package main

// 994. 腐烂的橘子
func main() {
	grid := [][]int{
		{2, 1, 1},
		{1, 1, 0},
		{0, 1, 1},
	}
	grid = [][]int{
		{1},
		{2},
		{1},
		{2},
	}
	rotting := orangesRotting(grid)
	println(rotting)
}

func orangesRotting1(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return -1
	}
	X := len(grid)
	Y := len(grid[0])

	var generateIdx = func(i, j int) int {
		return i*Y + j
	}

	var parseIdx = func(idx int) (int, int) {
		x := idx / Y
		y := idx % Y
		return x, y
	}

	var inflectOrigins = func(i, j int) bool {
		if i < 0 || i > X-1 || j < 0 || j > Y-1 {
			return false
		}
		if grid[i][j] == 1 { // 被感染
			grid[i][j] = 2
			return true
		}
		return false
	}

	var queue []int
	infectNums := 0

	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			if grid[i][j] == 2 {
				queue = append(queue, generateIdx(i, j))
			}
		}
	}

	if len(queue) > 0 {
		infectNums = -1
	}

	for len(queue) > 0 {
		queueLen := len(queue)
		for i := 0; i < queueLen; i++ {
			x, y := parseIdx(queue[i])
			if inflectOrigins(x-1, y) {
				queue = append(queue, generateIdx(x-1, y))
			}
			if inflectOrigins(x+1, y) {
				queue = append(queue, generateIdx(x+1, y))
			}
			if inflectOrigins(x, y-1) {
				queue = append(queue, generateIdx(x, y-1))
			}
			if inflectOrigins(x, y+1) {
				queue = append(queue, generateIdx(x, y+1))
			}
		}
		queue = queue[queueLen:]
		infectNums++
	}

	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			if grid[i][j] == 1 {
				return -1
			}
		}
	}

	return infectNums
}

func orangesRotting(grid [][]int) int {
	// 广度优先遍历
	rottingNum := 0
	if len(grid) == 0 || len(grid[0]) == 0 {
		return rottingNum
	}
	X := len(grid)
	Y := len(grid[0])

	var generateIdx = func(x, y int) int {
		return x*Y + y
	}
	var parseIdx = func(idx int) (x, y int) {
		x = idx / Y
		y = idx % Y
		return x, y
	}
	var infectOranges = func(x, y int) bool {
		if x < 0 || x >= X || y < 0 || y >= Y {
			return false
		}
		if grid[x][y] == 1 {
			grid[x][y] = 2
			return true
		}
		return false
	}

	var queue []int

	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			if grid[i][j] == 2 { // 等于2
				idx := generateIdx(i, j)
				queue = append(queue, idx)
			}
		}
	}

	if len(queue) > 0 {
		rottingNum = -1
	}

	for len(queue) > 0 {
		currLen := len(queue)

		for i := 0; i < currLen; i++ {
			idx := queue[i]

			// 开始腐烂旁边的，并且判定
			x, y := parseIdx(idx)

			if infectOranges(x+1, y) {
				queue = append(queue, generateIdx(x+1, y))
			}
			if infectOranges(x, y+1) {
				queue = append(queue, generateIdx(x, y+1))
			}
			if infectOranges(x-1, y) {
				queue = append(queue, generateIdx(x-1, y))
			}
			if infectOranges(x, y-1) {
				queue = append(queue, generateIdx(x, y-1))
			}
		}
		queue = queue[currLen:]
		rottingNum++
		printGrid(grid)
	}

	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			if grid[i][j] == 1 { // 还有活口
				return -1
			}
		}
	}

	return rottingNum
}

func printGrid(grid [][]int) {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return
	}
	x := len(grid)
	y := len(grid[0])
	for i := 0; i < x; i++ {
		for j := 0; j < y; j++ {
			print(grid[i][j], ",")
		}
		println()
	}
	println()
}

// 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
//
//值 0 代表空单元格；
//值 1 代表新鲜橘子；
//值 2 代表腐烂的橘子。
//每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
//
//返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
//
//示例 1：
//
//输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
//输出：4
//示例 2：
//
//输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
//输出：-1
//解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
//示例 3：
//
//输入：grid = [[0,2]]
//输出：0
//解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
//
//提示：
//
//m == grid.length
//n == grid[i].length
//1 <= m, n <= 10
//grid[i][j] 仅为 0、1 或 2
